import { swap, testSort } from "hy-algokit";

/**
1. 核心思想
选择一个基准值（Pivot）：从数组中选择一个元素作为基准（通常选第一个、最后一个或中间元素）。
分区（Partition）：

将数组重新排列，使得所有小于基准的元素放在基准的左边。

所有大于基准的元素放在基准的右边。

基准值最终位于正确的位置（即排序后它应该在的位置）。

递归排序子数组：

对基准左边的子数组递归调用快速排序。

对基准右边的子数组递归调用快速排序。

2. 分区（Partition）的实现
分区是快速排序的核心步骤，常见的有 Lomuto 分区 和 Hoare 分区 两种方法。
（1）Lomuto 分区（较易理解）
选择最后一个元素作为基准（pivot = arr[right]）。

使用指针 i 记录小于 pivot 的边界。

遍历数组，将小于 pivot 的元素交换到 i 的位置，并递增 i。

最后将 pivot 交换到 i 的位置。
 */
// 快速排序函数
export default function quickSort(arr: number[]): number[] {
  function partition(left: number, right: number): number {
    // 选择中间元素作为基准值
    const pivotIndex = Math.floor((left + right) / 2);
    const pivot = arr[pivotIndex];
    
    // 将基准值移到最右边
    swap(arr, pivotIndex, right);
    
    let i = left;
    
    // 重新排列数组，小于pivot的放左边，大于的放右边
    for (let j = left; j < right; j++) {
      if (arr[j] < pivot) {
        swap(arr, i, j);
        i++;
      }
    }
    
    // 将基准值放回正确位置
    swap(arr, i, right);
    return i;
  }

  function sort(left: number, right: number) {
    if (left >= right) return;
    
    const pivotIndex = partition(left, right);
    sort(left, pivotIndex - 1);
    sort(pivotIndex + 1, right);
  }

  sort(0, arr.length - 1);
  return arr;
}

testSort(quickSort);

console.log(quickSort([-1, 0, 0, 0, 0, -9, -8, 99, 0, -65, 4, 3, 2, 1]));

export { quickSort };
